// 给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
// 请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。

//  

// 示例：

// matrix = [
//    [ 1,  5,  9],
//    [10, 11, 13],
//    [12, 13, 15]
// ],
// k = 8,

// 返回 13。
//  

// 提示：
// 你可以假设 k 的值永远是有效的，1 ≤ k ≤ n2 。

// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include <vector>
#include <algorithm>
using std::vector;
using std::sort;
// 直接排序
// 时间复杂度 O(N^2*logN)
// 空间复杂度 O(n^2)
class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        vector<int> res(n*n, 0);
        for (int i{0}; i < n; ++i) {
            for (int j{0}; j < n; ++j) {
                res[i*n+j] = matrix[i][j];
            }
        }
        sort(res.begin(), res.end());
        return res[k-1];
    }
};

#include <queue>
#include <functional>
using std::priority_queue;
using std::greater;
// 归并排序，n个数组归并，小根堆
// 时间复杂度 O(klogN)
// 空间复杂度 O(n)
class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        priority_queue<point, vector<point>, greater<point>> pq{};
        int n = matrix.size();
        for (int i{0}; i < n; ++i) {
            pq.emplace(matrix[i][0], i, 0);
        }
        for (int i{0}; i < k - 1; ++i) {
            point now = pq.top();
            pq.pop();
            if (now.y != n - 1) {
                pq.emplace(matrix[now.x][now.y + 1], now.x, now.y + 1);
            }
        }
        return pq.top().val;
    }
private:
    struct point{
        int val, x, y;
        point(int val, int x, int y) : val(val), x(x), y(y) {}
        bool operator> (const point& a) const {
            return this->val > a.val;
        }
    };
};

// 二分查找
// 时间复杂度 O(Nlog(r-l))
// 空间复杂度 O(1)
class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        int left = matrix[0][0];
        int right = matrix[n-1][n-1];
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (check(matrix, mid, k, n)) right = mid;
            else left = mid + 1;
        }
        return left;
    }
    bool check(const vector<vector<int>>& matrix,
               const int& mid,
               const int& k,
               const int& n) 
    {
        int i = n - 1;
        int j{0};
        int num{0};
        while (i >= 0 && j < n) {
            if (matrix[i][j] <= mid) {
                num += i + 1;
                ++j;
            } else --i;
        }
        return num >= k;
    }
};